#pragma once

#include <cstddef>
namespace ezstl {

// iterator category
// read only 这种迭代器所指的对象，不允许外界改变，readonly
struct input_iterator_tag {};
// write only
struct output_iterator_tag {};
// 允许写入型算法（replace）在此种迭代器所形成的区间上进行读写操作
struct forward_iterator_tag : public input_iterator_tag {};
// 允许逆向访问某个迭代器区间
struct bidirectional_iterator_tag : public forward_iterator_tag {};
// 支持 p++, p+n, p-n, p[n], p1-p2, p1<p2 操作
struct random_access_iterator_tag : public bidirectional_iterator_tag {};

template <typename Category, typename T, typename Distance = ptrdiff_t,
          typename Pointer = T *, typename Reference = T &>
struct iterator {
  using iterator_category = Category;
  using value_type = T;
  using difference_type = Distance;
  using pointer = Pointer;
  using reference = Reference;
};

template <typename Iter>
struct iterator_traits {
  using iterator_category = typename Iter::iterator_category;
  using value_type = typename Iter::value_type;
  using difference_type =
      typename Iter::difference_type;      // 表示两个迭代器之间距离
  using pointer = typename Iter::pointer;  //
  using reference = typename Iter::reference;
};

// Partial specialization for pointer types.
template <typename T>
struct iterator_traits<T *> {
  using iterator_category = random_access_iterator_tag;
  using value_type = T;
  using difference_type = ptrdiff_t;
  using pointer = T *;
  using reference = T &;
};

// Partial specialization for const pointer types.
template <typename T>
struct iterator_traits<const T *> {
  using iterator_category = random_access_iterator_tag;
  using value_type = T;
  using difference_type = ptrdiff_t;
  using pointer = const T *;
  using reference = const T &;
};

template <typename Iter>
__attribute__((__always_inline__)) inline constexpr
    typename iterator_traits<Iter>::iterator_category
    iterator_category(const Iter &) {
  return typename iterator_traits<Iter>::iterator_category();
}

template <typename Iter>
using __iter_category_t = typename iterator_traits<Iter>::iterator_category;

template <typename Iter>
__attribute__((__always_inline__)) inline constexpr
    typename iterator_traits<Iter>::difference_type *
    distance_type(const Iter &) {
  return static_cast<typename iterator_traits<Iter>::difference_type *>(0);
}

template <typename Iter>
__attribute__((__always_inline__)) inline constexpr
    typename iterator_traits<Iter>::value_type *
    value_type(const Iter &) {
  return static_cast<typename iterator_traits<Iter>::value_type *>(0);
}

// distance function

template <typename InputIterator>
inline typename iterator_traits<InputIterator>::difference_type __distance(
    InputIterator first, InputIterator last, input_iterator_tag) {
  typename iterator_traits<InputIterator>::difference_type n = 0;
  for (; first != last; ++first, ++n);
  return n;
}

template <typename RandomAccessIterator>
inline typename iterator_traits<RandomAccessIterator>::difference_type
__distance(RandomAccessIterator first, RandomAccessIterator last,
           random_access_iterator_tag) {
  return last - first;
}

template <typename InputIterator>
typename iterator_traits<InputIterator>::difference_type inline distance(
    InputIterator first, InputIterator last) {
  // return __distance(first, last, iterator_category(first));
  using category = typename iterator_traits<InputIterator>::iterator_category;
  return __distance(first, last, category());
}

// advance function
template <typename InputIterator, typename Distance>
inline void __advance(InputIterator it, Distance n, input_iterator_tag) {
  for (; n > 0; --n, ++it);
}

template <typename BidirectionalIterator, typename Distance>
inline void __advance(BidirectionalIterator it, Distance n,
                      bidirectional_iterator_tag) {
  if (n >= 0)
    for (; n > 0; --n, ++it);
  else
    for (; n > 0; --n, ++it);
}

template <typename RandomAccessIterator, typename Distance>
inline void __advance(RandomAccessIterator it, Distance n,
                      random_access_iterator_tag) {
  it += n;
}

template <typename InputIterator, typename Distance>
inline void advance(InputIterator &it, Distance n) {
  // __advance(it, n, iterator_category(it));
  using category = typename iterator_traits<InputIterator>::iterator_category;
  __advance(it, n, category());
}

}  // namespace ezstl